package com.xxwy.maxheap.practice.leetcode;

import com.xxwy.queue.PriorityQueue;

import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

/**
 * @author xxwy
 */
public class TopKFrequent {

    private class Frep implements Comparable<Frep> {
        public int e, freq;

        @Override
        public int compareTo(Frep another) {
            if (this.freq < another.freq) {
                return 1;
            } else if (this.freq > another.freq) {
                return -1;
            } else {
                return 0;
            }

        }

        public Frep(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i] + 1));
            } else {
                map.put(nums[i], 1);
            }
        }
        PriorityQueue<Frep> priorityQueue = new PriorityQueue<>();
        for (int key : map.keySet()) {
            if (priorityQueue.getSize() < k) {
                priorityQueue.enqueue(new Frep(key, map.get(key)));
            } else if (map.get(key) > priorityQueue.getFront().freq) {
                priorityQueue.dequeue();
                priorityQueue.enqueue(new Frep(key,map.get(key)));
            }
        }
        LinkedList<Integer> integers = new LinkedList<>();
        while (!priorityQueue.isEmpty()){
            integers.add(priorityQueue.dequeue().e);
        }
        return integers;
    }


}
